package airthmetic.exercise.dp;

public class _5_最长回文子串 {
    public static String longestPalindrome(String s) {
        /**
         1.确定状态参数/选择决策
         状态参数：原问题与子问题之间变化的值
         此题为s字符串的左右边界  s[1...i] s[1...j] 所以是两个边界两个状态参数
         选择/决策：做选择使状态参数变化并趋近于原问题的解
         2.定义dp数组(dp table)的含义
         int n = s.length();
         boolean[][] dp = new boolean[n][n];
         此题dp数组的含义是，当前位置是否为回文子串 dp[i][j] == true 为回文子串
         3.初始化dp数组
         对角线上都是回文子串，因为对角线上就是一个字符，一个字符也是回文子串
         i<=j的时候才能是回文子串,所以i>j的情况都为false
         此为初始化dp数组

         4.推导状态转移公式
         if(s[i] != s[j]){

         dp[i][j] = false;

         }else{
         if(j - i + 1 < 2){
         dp[i][j] = true;
         }else{
         dp[i][j] = dp[i+1][j-1];
         }
         }

         */

        //特殊判断
        if (s==null || s.length() < 2) {
            return s;
        }

        int n = s.length();
        char[] cs = s.toCharArray();
        boolean[][] dp = new boolean[n][n];

        for(int i=0; i<n; i++){
            dp[i][i] = true;
        }
        int begin = 0;
        int maxValue = 1;
        for(int i=n-1; i>=0; i--){
            for(int j=i+1; j<n; j++){
                if(cs[i] != cs[j]){
                    dp[i][j] = false;
                }else{
                    if(j - i  < 3){
                        dp[i][j] = true;
                    }else{
                        dp[i][j] = dp[i+1][j-1];
                    }
                }

                if(dp[i][j] && (j-i+1) > maxValue){
                    maxValue = j- i + 1;
                    begin = i;
                }
            }
        }

        return s.substring(begin,begin+maxValue);




    }



    public static String longestPalindrome2(String s) {
        /**
         因为问题具备重叠子问题和无后效性以及最优子结构。动态规划！

         1.确定状态参数和选择
         先思考什么是原问题 什么是子问题
         原问题：s1[0] s1[s.length() - 1] s1[i] s1[j]
         子问题：s1[0 + 1] s1[s.length() -1 -1]  s1[i+1] s1[j-1]
         子问题：s1[0 + 1] s1[s.length() -1 ]  s1[i+1] s1[j]   不是子问题
         子问题：s1[0] s1[s.length() -1 -1]  s1[i]   s1[j-1]   不是子问题

         状态参数：
         状态参数是在原问题与子问题之间不断变化的值
         此题有两个状态参数
         左右边界： left right

         选择/决策：
         做选择使状态参数不断变化并趋近于原问题的解
         for(int i=0; i<s.length(); i++){
         for(int j=0; j<s.length(); j++){

         }
         }

         2.定义dp table 的含义
         boolean[][] dp = new boolean[s.length()][s.length()];
         dp[i][j]表示以s1[i]开头 s1[j]结尾的字符串是否使回文子串


         3.初始化dp table
         单个字符是特殊的回文子串
         所以：
         for(int i=0; i<s.length(); i++){
         for(int j=0; j<s.length(); j++){
         dp[i][j] = true;
         }
         }

         如果 left > right不能成为一个字符串
         所以：
         for(int i=1; i<s.length(); i++){
         for(int j=0; j<i; j++){
         dp[i][j] = false;
         }
         }

         4.推导状态转移公式
         if(s1[left] != s1[right]){
         dp[left][right] = false;
         }else{
         if(s1[left] == s1[right]){
         if(j-1 - i+1 + 1 < 2){
         dp[left][right] = true;
         }else{
         dp[left][right] = dp[i+1][j-1];
         }
         }
         }
         结合dp table 发现不能逐行遍历，因为dp[i+1][j-1]可能还未求解
         i从n~0,j从0~n遍历
         */
        char[] s1 = s.toCharArray();
        int m = s1.length;
        boolean[][] dp = new boolean[m][m];
        for(int i=0; i<m; i++){
            dp[i][i] = true;
        }
        for(int i=1; i<m; i++){
            for(int j=0; j<i; j++){
                dp[i][j] = false;
            }
        }
        int startIndex =0;
        int max = 1;
        for(int i=m-1; i>=0; i--){
            for(int j=i+1; j<=m-1; j++){
                if(s1[i] != s1[j]){
                    dp[i][j] = false;
                }else{
                    if((j-1) - (i+1) + 1  < 2){
//                    if(j-1 - i+1 + 1  < 2){
                        dp[i][j] = true;
                    }else{
                        dp[i][j] = dp[i+1][j-1];
                    }
                    // 还是要判断 因为即便左右边界上是相同的，i+1 j-1不一定是回文子串
                    if(dp[i][j]){
                        if(j-i + 1 > max){
                            startIndex = i;
                            max = j-i+1;
                        }
                    }

                }
            }
        }

        return s.substring(startIndex, startIndex+max);

    }


    public static String longestPalindrome3(String s) {

        /**
         因为问题具备重叠子问题和无后效性以及最优子结构。 动态规划！
         重叠子问题：s1[i] s1[j] 被后续用到
         无后效性： s1[i] s1[j] 不会被后续的选择影响
         最优子结构：s1[i] s1[j] 独立并且可以被后续问题使用

         动态规划思考问题：
         1.确认状态参数和选择：
         先思考什么是原问题 什么是子问题
         原问题：s1[i] s1[j]
         子问题：s1[i+1] s1[j-1]

         状态参数:此题两个状态参数，s1[i] s1[j] 分别表示字符串的左右边界

         选择/决策：不断选择下标

         2.定义dp table的含义
         boolean[][] dp = new boolean[s.length()][s.length()];
         dp[i][j]表示 i开头j结尾的字符串是否是回文子串

         3.初始化 dp table
         单个字符也是一种特殊的回文子串 true
         i>j的时候不符合字符串的定义 false

         4.推导状态转移公式
         for(int i=0; i<s.length(); i++){
             for(int j=0; j<s.length(); j++){
                 if(s1[i] != s1[j]){
                     dp[i][j] == false;
                 }else{
                     if((j-1) - (i+1) + 1 < 2){
                        dp[i][j] = true;
                     }else{
                        dp[i][j] = dp[i+1][j-1];
                     }
                 }
             }
         }

         因为求解过程中发现 求解 dp[i][j] 只用到 dp[i+1][j-1] 但如果正向遍历可能还拿不到dp[i+1][j-1]的值(还未被求解)所以我们调整遍历方向
         for(int i=n-1; i>=0; i--){
             for(int j=i+1; j<n; j++){
                 if(s1[i] != s1[j]){
                     dp[i][j] == false;
                 }else{
                    if((j-1) - (i+1) + 1 < 2){
                        dp[i][j] = true;
                    }else{
                        dp[i][j] = dp[i+1][j-1];
                    }
                 }
             }
         }
         */

        char[] sc = s.toCharArray();
        int n = sc.length;
        boolean[][] dp = new boolean[n][n];
        for(int i=0; i<dp.length; i++){
            dp[i][i] = true;
        }
        int begin = 0;
        int max = 1;
        for(int i=n-1; i>=0; i--){
            for(int j=i+1; j<n; j++){
                if(sc[i] != sc[j]){
                    dp[i][j] = false;
                }else{
                    if((j-1) - (i+1) + 1 < 2){
                        dp[i][j] = true;
                    }else{
                        dp[i][j] = dp[i+1][j-1];
                    }


                    if(dp[i][j] && max < j-i+1){
                        begin = i;
                        max = j-i+1;
                    }
                }
            }
        }

        return s.substring(begin,begin+max);

    }


    // 状态压缩
    public String longestPalindrome4(String s) {
        /**
         因为问题具备重叠子问题和无后效性及最优子结构。 动态规划！
         动态规划思考问题：
         什么是原问题 什么是子问题
         原问题：s1[i]与s1[j]
         子问题：s1[i+1] 与 s1[j-1]

         1.确定状态参数和选择
         状态参数：在原问题与子问题之间不断变化的值
         此题为left下标与right下标

         选择/决策：此题为选择不同left 与 right下标

         2.定义dp table的含义
         boolean[][] dp = new boolean[s.length()][s.length()];
         dp[i][j] 表示 i开头 j结尾的子串是否是回文子串

         3.初始化dp table
         单个字符的字符串也是特殊的回文子串 true
         当i>j时不满足字符串的定义 false

         4.推到状态转移公式
         for(int i=0; i<s.length(); i++){
         for(int j=0; j<s.length(); j++){
         if(s1[i] != s1[j]){
         dp[i][j] = false;
         }else{
         if((j-1) - (i+1) + 1 < 2){
         dp[i][j] = true;
         }else{
         dp[i][j] = dp[i+1][j-1];
         }

         }
         }
         }

         */

        char[] s1 = s.toCharArray();
        boolean[] dp = new boolean[s.length()];
        int beginIndex = 0;
        int max = 1;
        for(int i=s.length() - 1; i>=0; i--){
            for(int j=s.length()-1; j>i; j--){
                if(s1[i] != s1[j]){
                    dp[j] = false;
                }else{
                    if(j-i < 3){
                        dp[j] = true;
                    }else{
                        dp[j] = dp[j-1];
                    }

                    if(dp[j] && j-i+1 > max){
                        beginIndex = i;
                        max = j-i+1;
                    }
                }

            }
        }

        return s.substring(beginIndex, beginIndex + max);

    }

    public static void main(String[] args) {
//        System.out.println(longestPalindrome("cbbd"));
//        System.out.println(longestPalindrome2("cbbd"));
        System.out.println(longestPalindrome3("aaaa"));

    }
}
